package com.demo.java.OD351_400.OD376;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【不开心的小朋友(B卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146233988
 */
public class OdMain {
    // 计算不开心的小孩数量
    public static int calculateUnhappyCount(int capacity, List<Integer> numbers) {
        List<Integer> playingKids = new ArrayList<>();  // 存储正在玩的孩子的ID列表
        Queue<Integer> waitingKids = new ArrayDeque<>();  // 存储等待的孩子的ID队列
        int unhappyCount = 0;  // 记录不开心的孩子数量

        // 遍历所有孩子的ID
        for (int kidId : numbers) {
            // 如果当前孩子正在玩，表示该孩子退出玩耍
            if (playingKids.contains(kidId)) {
                playingKids.remove(Integer.valueOf(kidId));  // 从正在玩的孩子中移除该孩子
                // 如果有孩子在等待，允许等待的孩子加入到正在玩的队列中
                if (!waitingKids.isEmpty()) {
                    playingKids.add(waitingKids.poll());  // 从等待队列中取出一个孩子加入正在玩队列
                } else {
                    capacity += 1;  // 如果没有等待的孩子，增加一个容量
                }
            }
            // 如果当前孩子在等待队列中，表示该孩子因为没有位置无法加入玩耍
            else if (waitingKids.contains(kidId)) {
                unhappyCount += 1;  // 增加不开心的孩子数量
                waitingKids.remove(Integer.valueOf(kidId));  // 从等待队列中移除该孩子
            }
            // 如果当前孩子既不在等待队列，也不在玩耍队列
            else {
                // 如果还有空闲容量，允许该孩子加入到正在玩的队列中
                if (capacity > 0) {
                    playingKids.add(kidId);  // 将孩子添加到正在玩的队列中
                    capacity -= 1;  // 减少容量
                } else {
                    waitingKids.add(kidId);  // 否则将孩子添加到等待队列中
                }
            }
        }

        return unhappyCount;  // 返回不开心的孩子数量
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);  // 创建Scanner对象，用于读取输入
        int capacity = scanner.nextInt();  // 读取容量值
        scanner.nextLine();  // 读取剩余的换行符
        List<Integer> numbers = new ArrayList<>();  // 用于存储孩子ID的列表

        // 读取整行输入，并将输入的数字分隔成一个个整数
        String line = scanner.nextLine();
        String[] tokens = line.split(" ");  // 按空格分割输入的数字
        for (String token : tokens) {
            numbers.add(Integer.parseInt(token));  // 将每个数字添加到numbers列表中
        }

        // 调用calculateUnhappyCount方法，计算不开心的孩子数量
        int unhappy = calculateUnhappyCount(capacity, numbers);
        // 输出不开心的孩子数量
        System.out.println(unhappy);
    }
}
